package mashibing.freshman.class07;

import java.util.ArrayList;
import java.util.List;

/**
 * 测试链接：https://leetcode.com/problems/path-sum-ii
 * 在二叉树上收集所有达标的路径和
 */
public class Code04_PathSumII {
	// 二叉树
	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;

		TreeNode(int val) {
			this.val = val;
		}
	}

	// 入口
	public static List<List<Integer>> pathSum(TreeNode root, int sum) {
		List<List<Integer>> ans = new ArrayList<>();
		if (root == null) {
			return ans;
		}
		ArrayList<Integer> path = new ArrayList<>();
		process(root, path, 0, sum, ans);
		return ans;// 指向地址
	}

	/**
	 * 递归求和为sum的所有路径
	 * @param x 二叉树root
	 * @param path 之前节点的路径,调完所有，path最终的size = 0
	 * @param preSum 累计和
	 * @param sum 要求的和
	 * @param ans 和为sum的所有路径，这个是要用的
	 */
	public static void process(TreeNode x, List<Integer> path, int preSum, int sum, List<List<Integer>> ans) {
		// 边界值，递归必有的跳出循环的条件
		if (x.left == null && x.right == null) {// 是叶节点
			if (preSum + x.val == sum) {// 如果 累加值+ 自己 = sum
				path.add(x.val);
				ans.add(copy(path));// 不拷贝的话，path改变，他也会跟着变
				path.remove(path.size() - 1);// 清理现场：要回上游去，需要删掉当前的节点
			}
			return;// 跳出方法
		}
		// x 非叶节点
		path.add(x.val);// 统一加
		preSum += x.val;// preSum是基本数据类型int，是值传递，加了以后不需要-，因为上游数据保持不变
		if (x.left != null) {// 左边不为空
			process(x.left, path, preSum, sum, ans);
		}
		if (x.right != null) {// 右边不为空
			process(x.right, path, preSum, sum, ans);
		}
		path.remove(path.size() - 1);// 统一删，path是引用传递
	}
	// 拷贝path
	public static List<Integer> copy(List<Integer> path) {
		List<Integer> ans = new ArrayList<>();
		for (Integer num : path) {
			ans.add(num);
		}
		return ans;
	}

	public static void main(String[] args) {
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.right = new TreeNode(3);
		ArrayList<Integer> path = new ArrayList<>();
		List<List<Integer>> ans = new ArrayList<>();
		int preSum =0;
		process(root, path, preSum, 4, ans);
		System.out.println(path.size());// path是引用传递
		System.out.println(preSum);// preSum是值传递
	}
}
